#include<stdio.h>

/*
    快速排序，先找中间
*/

const int numbers_size=8;
int numbers[]={49,38,65,97,76,13,27,49};
void swap(int* a,int* b){//交换原变量的值
    int temp=*a;
    (*a)=*b;
    (*b)=temp;
}

void show(int array[],int n){
    for(int i=0;i<n;i++){
        printf("%d ",array[i]);
    }
    printf("\n");
}

//返回枢纽下标，枢纽就是能把数组分为两部分，前一部分比枢纽值小，后一部分比枢纽大
//实际上这个枢纽一般选取数组第一个元素，然后把这个枢纽移动到合适的位置，最后返回这个位置
int Paritition(int array[],int left,int right){
    int pivot=array[left];//最左侧的元素作为初始值，挖坑
    while (left<right)
    {
        while(left<right&&pivot<=array[right]){//交换左右元素
            --right;
        }
        array[left]=array[right];//注意，这里并不是交换两个元素，因为有一个挖坑已经赋值给pivot保存，所以这里是赋值
        printf("<<<<<-----查找，交换两个元素%d，%d\t",left,right);
        show(array,numbers_size);
        while (left<right&&array[left]<pivot)
        {
            ++left;
        }
        array[right]=array[left];
        printf("------>>>>查找，交换两个元素%d，%d\t",left,right);
        show(array,numbers_size);
    }
    return left;
    
}
/*
49,38,65,97,76,13,27,49对于这一组数据，现在将第一个元素49作为枢纽，这里的规则是如果两个数字相等，就不交换
第一轮paritition,pviot=49(这里叫做key比较合适，因为是值，而不是下标),left=0 right=7
49从右向左比较，49=49  right--变成6  
    49>27 跳出循环，交换left 和 right的元素 现在变成了27,38,65,97,76,13,49,49
    交换之后，从另一边开始
    49>27 left->1
    49>38 left->2
    49<65 跳出循环 交换right 和 left元素49和65，27,38,49,97,76,13,65,49
    这里比较特殊，因为第一个元素正好也是49，从右向左的时候交换，把right下标对应的值变成了49，所以看起来比较怪
49从左向右比较, 49=49  left
*/
int count=0;
void quickSort(int array[],int left,int right){
    count++;
    if(left<right){
        printf("第%d次递归\n",count);
        int pivot=Paritition(array,left,right);
        
        quickSort(array,left,pivot-1);
        quickSort(array,pivot+1,right);
    }
    
}
int main(void){
    quickSort(numbers,0,numbers_size-1);
    printf("结果输出：\n");
    show(numbers,numbers_size);

    return 0;
}